{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Height Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMinHeightTrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小高度树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。</p>\n",
    "\n",
    "<p>给你一棵包含&nbsp;<code>n</code>&nbsp;个节点的树，标记为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code> 。给定数字&nbsp;<code>n</code>&nbsp;和一个有 <code>n - 1</code> 条无向边的 <code>edges</code>&nbsp;列表（每一个边都是一对标签），其中 <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 表示树中节点 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 之间存在一条无向边。</p>\n",
    "\n",
    "<p>可选择树中任何一个节点作为根。当选择节点 <code>x</code> 作为根节点时，设结果树的高度为 <code>h</code> 。在所有可能的树中，具有最小高度的树（即，<code>min(h)</code>）被称为 <strong>最小高度树</strong> 。</p>\n",
    "\n",
    "<p>请你找到所有的 <strong>最小高度树</strong> 并按 <strong>任意顺序</strong> 返回它们的根节点标签列表。</p>\n",
    "树的 <strong>高度</strong> 是指根节点和叶子节点之间最长向下路径上边的数量。\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/01/e1.jpg\" style=\"height: 213px; width: 800px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, edges = [[1,0],[1,2],[1,3]]\n",
    "<strong>输出：</strong>[1]\n",
    "<strong>解释：</strong>如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/01/e2.jpg\" style=\"height: 321px; width: 800px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]\n",
    "<strong>输出：</strong>[3,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li>所有 <code>(a<sub>i</sub>, b<sub>i</sub>)</code> 互不相同</li>\n",
    "\t<li>给定的输入 <strong>保证</strong> 是一棵树，并且 <strong>不会有重复的边</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-height-trees](https://leetcode.cn/problems/minimum-height-trees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-height-trees](https://leetcode.cn/problems/minimum-height-trees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[1,0],[1,2],[1,3]]', '6\\n[[3,0],[3,1],[3,2],[3,4],[5,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "\n",
    "        q = [i for i, d in enumerate(deg) if d == 1]\n",
    "        remainNodes = n\n",
    "        while remainNodes > 2:\n",
    "            remainNodes -= len(q)\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                for y in g[x]:\n",
    "                    deg[y] -= 1\n",
    "                    if deg[y] == 1:\n",
    "                        q.append(y)\n",
    "        return q\n",
    "\n",
    "\n",
    "        # nodes = {i:0 for i in range(n)}\n",
    "        # for edge in edges:\n",
    "        #     nodes[edge[0]] += 1\n",
    "        #     nodes[edge[1]] += 1\n",
    "\n",
    "        # while len(nodes)>2:\n",
    "        #     leaves = []\n",
    "        #     for node in nodes.keys():\n",
    "        #         if nodes[node] ==1:\n",
    "        #             leaves.append(node)\n",
    "\n",
    "        #     cutting_edges = []\n",
    "        #     for edge in edges:\n",
    "        #         if edge[0] in leaves or edge[1] in leaves:\n",
    "        #             nodes[edge[0]] -= 1\n",
    "        #             nodes[edge[1]] -= 1\n",
    "        #         if edge[0] not in leaves and edge[1] not in leaves:\n",
    "        #             cutting_edges.append(edge)\n",
    "            \n",
    "        #     for leave in leaves:\n",
    "        #         nodes.pop(leave)\n",
    "                \n",
    "                \n",
    "        #     edges.clear()\n",
    "        #     edges.extend(cutting_edges)\n",
    "\n",
    "            \n",
    "        # return list(nodes.keys())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n==1:\n",
    "            return [0]\n",
    "\n",
    "        d = [0]*n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            d[x] += 1\n",
    "            d[y] += 1\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "\n",
    "        q = [i for i in range(n) if d[i]==1]\n",
    "        count = n\n",
    "        while count > 2:\n",
    "            count -= len(q)\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                for y in g[x]:\n",
    "                    d[y] -= 1\n",
    "                    if d[y] == 1:\n",
    "                        q.append(y)\n",
    "        return q\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        neighbor_list = [[] for _ in range(n)]\n",
    "        degree = [0 for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            p, q = edge\n",
    "            neighbor_list[p].append(q)\n",
    "            degree[p] += 1\n",
    "            neighbor_list[q].append(p)\n",
    "            degree[q] += 1\n",
    "        queue = []\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1:\n",
    "                queue.append(i)\n",
    "        while n > 2:\n",
    "            leng = len(queue)\n",
    "            n -= leng\n",
    "            for i in range(leng):\n",
    "                tmp = queue.pop(0)\n",
    "                for ele in neighbor_list[tmp]:\n",
    "                    degree[ele] -= 1\n",
    "                    if degree[ele] == 1:\n",
    "                        queue.append(ele)\n",
    "        return queue\n",
    "\n",
    "    def findMinHeightTrees1(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        neighbor_list = [[] for _ in range(n)]\n",
    "        degree = [0 for _ in range(n)]\n",
    "        for ele in edges:\n",
    "            a, b = ele\n",
    "            neighbor_list[a].append(b)\n",
    "            degree[a] += 1\n",
    "            neighbor_list[b].append(a)\n",
    "            degree[b] += 1\n",
    "        # print(degree)\n",
    "        \n",
    "        queue = []\n",
    "        for i in range(n):\n",
    "            # print(i)\n",
    "            if degree[i] == 1:\n",
    "                # print('T')\n",
    "                queue.append(i)\n",
    "            else:\n",
    "                continue\n",
    "        # print(queue)\n",
    "        while n > 2:\n",
    "            leng = len(queue)\n",
    "            n -= leng\n",
    "            for i in range(leng):\n",
    "                tmp = queue.pop(0)\n",
    "                for ele in neighbor_list[tmp]:\n",
    "                    degree[ele] -= 1\n",
    "                    if degree[ele] == 1:\n",
    "                        queue.append(ele)\n",
    "        return queue\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        d = {}\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        ll = [0]*n\n",
    "        for a in edges:\n",
    "            if a[0] not in d:\n",
    "                d[a[0]] = []\n",
    "            if a[1] not in d:\n",
    "                d[a[1]] = []\n",
    "            d[a[0]].append(a[1])\n",
    "            d[a[1]].append(a[0])\n",
    "            ll[a[0]] += 1\n",
    "            ll[a[1]] += 1\n",
    "        l = []\n",
    "        for i in range(n):\n",
    "            if ll[i] == 1:\n",
    "                l.append(i)\n",
    "        while l:\n",
    "            tmp = []\n",
    "            for j in l:\n",
    "                for z in d[j]:\n",
    "                    ll[z]-=1\n",
    "                    if ll[z] == 1:\n",
    "                        tmp.append(z)\n",
    "            if tmp == []:\n",
    "                return l\n",
    "            l = tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n==1:\n",
    "            return [0]\n",
    "        connect=collections.defaultdict(list)\n",
    "        inDegree=[0]*n\n",
    "        for a,b in edges:\n",
    "            connect[a].append(b)\n",
    "            connect[b].append(a)\n",
    "            inDegree[a]+=1\n",
    "            inDegree[b]+=1\n",
    "        q=deque()\n",
    "        for i in range(n):\n",
    "            if inDegree[i]==1:\n",
    "                q.append(i)\n",
    "        res=[]\n",
    "        print(q)\n",
    "        while q:\n",
    "            res=[]\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                res.append(node)\n",
    "                for neighbor in connect[node]:\n",
    "                    inDegree[neighbor]-=1\n",
    "                    if inDegree[neighbor]==1:\n",
    "                        q.append(neighbor)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        \"\"\" TopSort\n",
    "        \"\"\"\n",
    "\n",
    "        if not edges:\n",
    "            return [0]\n",
    "        \n",
    "        # UniG \n",
    "        G = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        for u, v in edges:\n",
    "            G[u].append(v)\n",
    "            G[v].append(u) \n",
    "            indeg[u] += 1 \n",
    "            indeg[v] += 1 \n",
    "        \n",
    "        queue = collections.deque([i for i, j in indeg.items() if indeg[i]==1])\n",
    "\n",
    "        while n > 2:\n",
    "            len_q = len(queue)\n",
    "            for _ in range(len_q):\n",
    "                x = queue.popleft()\n",
    "                indeg[x] = 0 \n",
    "                n -= 1 \n",
    "                for v in G[x]:\n",
    "                    indeg[v] -= 1 \n",
    "                    if indeg[v] == 1:\n",
    "                        queue.append(v) \n",
    "        return list(queue)\n",
    "\n",
    "        # all_dists = [0] * n \n",
    "\n",
    "        # # post-order dfs for max tree diameter \n",
    "        # def dfs(x, fa):\n",
    "        #     depth = 0 \n",
    "        #     for v in G[x]:\n",
    "        #         if v != fa:\n",
    "        #             depth = max(depth, dfs(v, x)+1)\n",
    "        #     return depth \n",
    "        \n",
    "        # for i in range(n):\n",
    "        #     all_dists[i] = dfs(i, -1)\n",
    "\n",
    "        # return [i for i, j in enumerate(all_dists) if j == min(all_dists)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # if n == 1:\n",
    "        #     return [0]\n",
    "\n",
    "        # g = [[] for _ in range(n)]\n",
    "        # deg = [0] * n\n",
    "        # for x, y in edges:\n",
    "        #     g[x].append(y)\n",
    "        #     g[y].append(x)\n",
    "        #     deg[x] += 1\n",
    "        #     deg[y] += 1\n",
    "\n",
    "        # q = [i for i, d in enumerate(deg) if d == 1]\n",
    "        # remainNodes = n\n",
    "        # while remainNodes > 2:\n",
    "        #     remainNodes -= len(q)\n",
    "        #     tmp = q\n",
    "        #     q = []\n",
    "        #     for x in tmp:\n",
    "        #         for y in g[x]:\n",
    "        #             deg[y] -= 1\n",
    "        #             if deg[y] == 1:\n",
    "        #                 q.append(y)\n",
    "        # return q\n",
    "\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        nodes = {i:0 for i in range(n)}\n",
    "        graphs = defaultdict(list)\n",
    "        for edge in edges:\n",
    "            nodes[edge[0]] += 1\n",
    "            nodes[edge[1]] += 1\n",
    "            graphs[edge[0]].append(edge[1])\n",
    "            graphs[edge[1]].append(edge[0])\n",
    "        \n",
    "        remainNodes = n\n",
    "        leaves = [ i for i, d in nodes.items() if d ==1]\n",
    "        while remainNodes>2:\n",
    "            \n",
    "            remainNodes -= len(leaves)\n",
    "            tmp = leaves\n",
    "            leaves = []\n",
    "\n",
    "            for node in tmp:\n",
    "                for neighbor in graphs[node]:\n",
    "                    nodes[neighbor] -= 1\n",
    "                    if nodes[neighbor] == 1:\n",
    "                        leaves.append(neighbor)\n",
    "        return leaves\n",
    "                \n",
    "                \n",
    "        #     edges.clear()\n",
    "        #     edges.extend(cutting_edges)\n",
    "\n",
    "            \n",
    "        # return list(nodes.keys())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self, n, nodes, vis, ins):\n",
    "        q = []\n",
    "        ren = n\n",
    "        for i in range(n):\n",
    "            if ins[i] == 1:\n",
    "                q.append(i)\n",
    "        while ren > 2:\n",
    "            ren -= len(q)\n",
    "            q_new = []\n",
    "            for x in q:\n",
    "                vis[x] = 1\n",
    "                for i in nodes[x]:\n",
    "                    ins[i] -= 1\n",
    "                    if vis[i] == 0 and ins[i] == 1:\n",
    "                        q_new.append(i)\n",
    "            q = q_new\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if vis[i] == 0:\n",
    "                res.append(i)\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        nodes = {}\n",
    "        vis = {}\n",
    "        ins = {}\n",
    "        for i in range(n):\n",
    "            nodes[i] = []\n",
    "            vis[i] = 0\n",
    "            ins[i] = 0\n",
    "        for x in edges:\n",
    "            a,b = x\n",
    "            nodes[a].append(b)\n",
    "            nodes[b].append(a)\n",
    "            ins[a] += 1\n",
    "            ins[b] += 1\n",
    "        return self.bfs(n, nodes, vis, ins)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        #first find the node has indegree of 1(meaing the most edged nodes)\n",
    "        degree = [0 for _ in range(n)]\n",
    "        neighbors = defaultdict(list) # all the neighbors of the \n",
    "        # outdegree = [0 for _ in range(n)]\n",
    "\n",
    "        for origin,target in edges:\n",
    "            neighbors[origin].append(target)\n",
    "            neighbors[target].append(origin)\n",
    "            degree[origin] += 1\n",
    "            degree[target] += 1\n",
    "        # print(degree)\n",
    "        # the edge nodes\n",
    "        queue = [i for i in range(len(degree)) if degree[i] == 1]\n",
    "        # BFS on the edge node and \n",
    "        # seen = set()\n",
    "        print(neighbors)\n",
    "        res = [0]\n",
    "        while queue:\n",
    "            level_breath = len(queue)\n",
    "            res = []\n",
    "\n",
    "            for i in range(level_breath):\n",
    "                cur = queue.pop(0) # bfs pop left most\n",
    "                nbs = neighbors[cur]\n",
    "                res.append(cur)\n",
    "                for n in nbs:\n",
    "                    #degree - 1\n",
    "                    degree[n] -= 1\n",
    "                    if degree[n] == 1:\n",
    "                        #join in the queue\n",
    "                        queue.append(n)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        adjGraph = [[] for _ in range(n)]\n",
    "        inDegrees = [0] * n\n",
    "        visited = set()\n",
    "        for u, v in edges:\n",
    "            adjGraph[u].append(v)\n",
    "            adjGraph[v].append(u)\n",
    "            inDegrees[u] += 1\n",
    "            inDegrees[v] += 1\n",
    "        queue = deque(node for node in range(n) if inDegrees[node] == 1)\n",
    "        while queue and n - len(visited) > 2:\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                visited.add(cur)\n",
    "                for child in adjGraph[cur]:\n",
    "                    if child in visited:\n",
    "                        continue\n",
    "                    inDegrees[child] -= 1\n",
    "                    if inDegrees[child] == 1:\n",
    "                        queue.append(child)\n",
    "        return [i for i in range(n) if i not in visited]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        degree = [0]*n #节点的度\n",
    "        result = set([x for x in range(n)])  #待选节点，一开始时全部节点，然后将叶子节点逐层删掉\n",
    "        if(not n > 2):\n",
    "            return list(result)\n",
    "        graph = [[] for x in range(n)]  #构建地图和节点的度\n",
    "        for node1,node2 in edges:\n",
    "            graph[node1].append(node2)\n",
    "            graph[node2].append(node1)\n",
    "            degree[node1] += 1\n",
    "            degree[node2] += 1\n",
    "        queue = []\n",
    "        for cur in range(n): #初始入队，将叶子节点（节点度为1的节点）入队\n",
    "            if (degree[cur] == 1):\n",
    "                queue.append(cur)\n",
    "                result.remove(cur) #入队说明该节点不可能成为根节点了。\n",
    "        while len(result) > 2:\n",
    "            length = len(queue) #获取队列的个数，主要是为了一层一层的遍历\n",
    "            for _ in range(length):\n",
    "                cur = queue.pop(0)\n",
    "                for next in graph[cur]:\n",
    "                    degree[next] -= 1\n",
    "                    if(degree[next] == 1):\n",
    "                        queue.append(next)\n",
    "                        result.remove(next)\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1 and not edges:\n",
    "            return [0]\n",
    "        inedge = [0] * n\n",
    "        graph = collections.defaultdict(dict)\n",
    "\n",
    "        for i, j in edges:\n",
    "            graph[i][j] = 1\n",
    "            graph[j][i] = 1\n",
    "            inedge[i] += 1\n",
    "            inedge[j] += 1\n",
    "        \n",
    "        q = [i for i in range(n) if inedge[i] == 1]\n",
    "        while n > 2:\n",
    "            n -= len(q)\n",
    "            res = []\n",
    "            for node in q:\n",
    "                for cnode in graph[node].keys():\n",
    "                    inedge[cnode] -= 1\n",
    "                    if inedge[cnode] == 1:\n",
    "                        res.append(cnode)\n",
    "            q = res\n",
    "        return q\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        tree_dict = dict()\n",
    "        in_out = [0] * n\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        for a, b in edges:\n",
    "            in_out[a] += 1\n",
    "            in_out[b] += 1\n",
    "            if a in tree_dict:\n",
    "                tree_dict[a].append(b)\n",
    "            else:\n",
    "                tree_dict[a] = [b]\n",
    "            if b in tree_dict:\n",
    "                tree_dict[b].append(a)\n",
    "            else:\n",
    "                tree_dict[b] = [a]\n",
    "        q = deque()\n",
    "        for i, v in enumerate(in_out):\n",
    "            if v == 1:\n",
    "                q.append(i)\n",
    "\n",
    "        ans = []\n",
    "        vis = set()\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            ans = []\n",
    "            for k in range(l):\n",
    "                j = q.popleft()\n",
    "                ans.append(j)\n",
    "                if j in tree_dict:\n",
    "                    ss = [t for t in tree_dict[j] if t not in vis]\n",
    "                    for n in ss:\n",
    "                        in_out[n] -= 1\n",
    "                        if in_out[n] == 1:\n",
    "                            q.append(n)\n",
    "                            vis.add(n)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        g = defaultdict(list)\n",
    "        indeg = [0] * n\n",
    "        for v,w in edges:\n",
    "            g[w].append(v)\n",
    "            g[v].append(w)\n",
    "            indeg[v] += 1\n",
    "            indeg[w] += 1\n",
    "        \n",
    "        vis = set()\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if indeg[i] == 1:\n",
    "                q.append(i)\n",
    "                vis.add(i)\n",
    "\n",
    "        while q:\n",
    "            if len(vis) == n:\n",
    "                return list(q)\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                v = q.popleft()\n",
    "                for w in g[v]:\n",
    "                    indeg[w] -= 1\n",
    "            \n",
    "            for i in range(n):\n",
    "                if i not in vis and indeg[i] <= 1:\n",
    "                    vis.add(i)\n",
    "                    q.append(i)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        neighbors=[set() for x in range(n)]\n",
    "        for a,b in edges:\n",
    "            neighbors[a].add(b)\n",
    "            neighbors[b].add(a)\n",
    "\n",
    "        remain_points=n\n",
    "        leafs=[]\n",
    "        for i in range(n):\n",
    "            if len(neighbors[i])<=1:\n",
    "                leafs.append(i)\n",
    "\n",
    "        while len(leafs)!=remain_points:\n",
    "            new_leafs=[]\n",
    "            for leaf in leafs:\n",
    "                for b in neighbors[leaf]:\n",
    "                    neighbors[b].remove(leaf)\n",
    "                    if len(neighbors[b])==1:\n",
    "                        new_leafs.append(b)\n",
    "                remain_points-=1\n",
    "            leafs=new_leafs\n",
    "        return leafs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n==1:\n",
    "            return [0]\n",
    "        g = [set() for _ in range(n)]\n",
    "        ins = [0]*n\n",
    "        for x,y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        q = deque([i for i in range(n) if len(g[i]) == 1])\n",
    "        while len(q)>0:\n",
    "            l = len(q)\n",
    "            ze = list(q)\n",
    "            for _ in range(l):\n",
    "                h = q.popleft()\n",
    "                for nei in g[h]:\n",
    "                    g[nei].remove(h)\n",
    "                    if len(g[nei]) == 1:\n",
    "                        q.append(nei)\n",
    "        return ze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 处理1个节点的特殊情况\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        # 处理2个结点的特殊情况\n",
    "        if n == 2:\n",
    "            return [0, 1]\n",
    "\n",
    "        # 构造图，并统计每个节点的相邻节点数量\n",
    "        graph = collections.defaultdict(set)\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].add(edge[1])\n",
    "            graph[edge[1]].add(edge[0])\n",
    "\n",
    "        # 广度优先搜索队列\n",
    "        queue = collections.deque()\n",
    "        for i, edge in graph.items():\n",
    "            if len(edge) == 1:\n",
    "                queue.append(i)\n",
    "\n",
    "        while queue:\n",
    "            n -= len(queue)\n",
    "            for _ in range(len(queue)):\n",
    "                # 能遍历到i时，说明i只有一条邻边\n",
    "                i = queue.popleft()\n",
    "                j = graph[i].pop()\n",
    "                graph[j].remove(i)\n",
    "                if len(graph[j]) == 1:\n",
    "                    queue.append(j)\n",
    "\n",
    "            if n == 1 or n == 2:\n",
    "                return list(queue)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        \"\"\"METHOD0 穷举\"\"\"    \n",
    "        # if n == 1:\n",
    "        #     return [0]\n",
    "        # # construct graph\n",
    "        # graph = collections.defaultdict(list)\n",
    "        # for e0, e1 in edges:\n",
    "        #     graph[e0].append(e1)\n",
    "        #     graph[e1].append(e0)      \n",
    "        # ans = [[-1, float('inf')]]\n",
    "        # for N in range(n):\n",
    "        #     # BFS\n",
    "        #     queue = [N]\n",
    "        #     opened = set([i for i in range(n)])\n",
    "        #     d = 0\n",
    "        #     while len(queue) > 0:\n",
    "        #         length = len(queue)\n",
    "        #         for _ in range(length):\n",
    "        #             num = queue.pop(0)\n",
    "        #             opened.remove(num)\n",
    "        #             for nxt in graph[num]:\n",
    "        #                 # 不访问已展开过的节点\n",
    "        #                 if nxt in opened:\n",
    "        #                     queue.append(nxt)\n",
    "        #         d += 1\n",
    "        #     if d < ans[0][1]:\n",
    "        #         ans = [[N, d]]\n",
    "        #     elif d == ans[0][1]:\n",
    "        #         ans.append([N, d])\n",
    "        # return [n[0] for n in ans]\n",
    "    \n",
    "        \"\"\"METHOD1 利用图论性质\"\"\"\n",
    "        # if n == 1:\n",
    "        #     return [0]\n",
    "        # # construct graph\n",
    "        # graph = collections.defaultdict(list)\n",
    "        # for e0, e1 in edges:\n",
    "        #     graph[e0].append(e1)\n",
    "        #     graph[e1].append(e0)\n",
    "\n",
    "        # parents = [0] * n\n",
    "        # d_max, nodeS = 0, -1\n",
    "        # def dfs(num, caller, d):\n",
    "        #     nonlocal d_max, nodeS\n",
    "        #     if d > d_max:\n",
    "        #         d_max, nodeS = d, num\n",
    "        #     parents[num] = caller\n",
    "        #     for nxt in graph[num]:\n",
    "        #         if nxt != caller:\n",
    "        #             dfs(nxt, num, d+1)\n",
    " \n",
    "        # START = 0\n",
    "        # dfs(START, -1, 1)\n",
    "        # d_max = 0\n",
    "        # dfs(nodeS, -1, 1)\n",
    "\n",
    "        # # print the path\n",
    "        # path1 = []\n",
    "        # while nodeS != -1:\n",
    "        #     path1.append(nodeS)\n",
    "        #     nodeS = parents[nodeS]\n",
    "\n",
    "        # l = len(path1)\n",
    "        # if l % 2 == 0:\n",
    "        #     return [path1[l//2-1], path1[l//2]]\n",
    "        # else:\n",
    "        #     return [path1[l//2]]\n",
    "\n",
    "        \"\"\"METHOD2 基于indegree和拓扑排序思想的BFS\"\"\"\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        # construct graph\n",
    "        graph = collections.defaultdict(list)\n",
    "        for e0, e1 in edges:\n",
    "            graph[e0].append(e1)\n",
    "            graph[e1].append(e0)\n",
    "        # measure indegrees\n",
    "        Indeg = [0] * n\n",
    "        for e0, e1 in edges:\n",
    "            Indeg[e0] += 1\n",
    "            Indeg[e1] += 1\n",
    "\n",
    "        OPEN = set([i for i in range(n)])\n",
    "        while True:\n",
    "            CUT = set()\n",
    "            for node in OPEN:\n",
    "                if Indeg[node] == 1:\n",
    "                    CUT.add(node)\n",
    "            if len(CUT) == 0 or len(OPEN) == 2:\n",
    "                return list(OPEN)\n",
    "            for node in CUT:\n",
    "                for nxt in graph[node]:\n",
    "                    Indeg[nxt] -= 1\n",
    "            OPEN = OPEN - CUT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict,deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges):\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        side_record = defaultdict(int)\n",
    "        path_record = defaultdict(set)\n",
    "        for n1, n2 in edges:\n",
    "            side_record[n1] += 1\n",
    "            side_record[n2] += 1\n",
    "            path_record[n1].add(n2)\n",
    "            path_record[n2].add(n1)\n",
    "        leaf_nodes = deque([node for node in side_record if side_record[node] == 1])\n",
    "        while n > 2:\n",
    "            n-=len(leaf_nodes)\n",
    "            for _ in range(len(leaf_nodes)):\n",
    "                node = leaf_nodes.popleft()\n",
    "                side_record.pop(node)\n",
    "                for nd in path_record[node]:\n",
    "                    side_record[nd] -= 1\n",
    "                    if side_record[nd]==1:\n",
    "                        leaf_nodes.append(nd)\n",
    "                    path_record[nd].remove(node)\n",
    "        return list(leaf_nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges):\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        side_record = defaultdict(int)\n",
    "        path_record = defaultdict(set)\n",
    "        for n1, n2 in edges:\n",
    "            side_record[n1] += 1\n",
    "            side_record[n2] += 1\n",
    "            path_record[n1].add(n2)\n",
    "            path_record[n2].add(n1)\n",
    "        while len(side_record) > 2:\n",
    "            leaf_nodes = []\n",
    "            for node in list(side_record.keys()):\n",
    "                if side_record[node] == 1:\n",
    "                    leaf_nodes.append(node)\n",
    "            for node in leaf_nodes:\n",
    "                side_record.pop(node)\n",
    "                for nd in path_record[node]:\n",
    "                    side_record[nd] -= 1\n",
    "                    path_record[nd].remove(node)\n",
    "        return list(side_record.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1: return [0]\n",
    "\n",
    "        nodeDegree = {}\n",
    "        neighbors = {}\n",
    "        for x,y in edges:\n",
    "            if x not in neighbors:\n",
    "                neighbors[x] = set()\n",
    "                nodeDegree[x] = 0\n",
    "            if y not in neighbors:\n",
    "                neighbors[y] = set()\n",
    "                nodeDegree[y] = 0\n",
    "\n",
    "            nodeDegree[x] += 1\n",
    "            nodeDegree[y] += 1\n",
    "\n",
    "            neighbors[x].add(y)\n",
    "            neighbors[y].add(x)\n",
    "\n",
    "        outerLoop = deque()\n",
    "        for node in nodeDegree:\n",
    "            if nodeDegree[node] == 1:\n",
    "                outerLoop.append(node)\n",
    "        \n",
    "        while len(outerLoop): \n",
    "            size = len(outerLoop)\n",
    "            res = []\n",
    "            for i in range(size):\n",
    "                nodeRemoved = outerLoop.popleft()\n",
    "                res.append(nodeRemoved)\n",
    "                for neighbor in neighbors[nodeRemoved]:\n",
    "                    nodeDegree[neighbor] -= 1\n",
    "                    neighbors[neighbor].remove(nodeRemoved)\n",
    "                    if nodeDegree[neighbor] == 1:\n",
    "                        outerLoop.append(neighbor)\n",
    "\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 处理特殊情况\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "\n",
    "        # 构建图的邻接表\n",
    "        graph = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "\n",
    "        # 初始化叶子节点集合\n",
    "        leaves = {node for node in graph if len(graph[node]) == 1}\n",
    "\n",
    "        # 逐步缩小叶子节点集合，直到剩下最后的根节点或根节点组合\n",
    "        while len(graph) > 2:\n",
    "            new_leaves = set()\n",
    "            for leaf in leaves:\n",
    "                neighbor = graph[leaf].pop()\n",
    "                graph[neighbor].remove(leaf)\n",
    "\n",
    "                if len(graph[neighbor]) == 1:\n",
    "                    new_leaves.add(neighbor)\n",
    "\n",
    "                del graph[leaf]\n",
    "\n",
    "            leaves = new_leaves\n",
    "\n",
    "        return list(leaves)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n==1:\n",
    "            return [0]\n",
    "        back = {}\n",
    "        for a, b in edges:\n",
    "            if a not in back:\n",
    "                back[a] = set()\n",
    "            back[a].add(b)\n",
    "            if b not in back:\n",
    "                back[b] = set()\n",
    "            back[b].add(a)\n",
    "        stack = []\n",
    "        for key, val in back.items():\n",
    "            if len(val) == 1:\n",
    "                stack.append(key)\n",
    "        while back:\n",
    "            if len(back) == 1 or len(back) == 2:\n",
    "                break\n",
    "            w = []\n",
    "            tem = []\n",
    "            for i in stack:\n",
    "                for j in back[i]:\n",
    "                    back[j].remove(i)\n",
    "            for ke, val in back.items():\n",
    "                if len(val) == 1 and ke not in stack:\n",
    "                    w.append(ke)\n",
    "            c = set(stack)\n",
    "            for i in c:\n",
    "                if i in back:\n",
    "                    del back[i]\n",
    "            stack = w\n",
    "        ans = list(back.keys())\n",
    "        ans.sort()\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges):\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        grep = dict()\n",
    "        grep_count = dict()\n",
    "        for i, j in edges:\n",
    "            if i not in grep:\n",
    "                grep[i] = set()\n",
    "            if j not in grep:\n",
    "                grep[j] = set()\n",
    "            grep[i].add(j)\n",
    "            grep[j].add(i)\n",
    "            grep_count[i] = grep_count.get(i, 0) + 1\n",
    "            grep_count[j] = grep_count.get(j, 0) + 1\n",
    "        leaf = set()\n",
    "        for i in list(grep_count):\n",
    "            if grep_count[i] == 1:\n",
    "                leaf.add(i)\n",
    "                grep_count.pop(i)\n",
    "        while grep_count:\n",
    "            new_leaf = set()\n",
    "            for i in leaf:\n",
    "                for j in grep[i]:\n",
    "                    if j in grep_count:\n",
    "                        grep_count[j] -= 1\n",
    "                        if grep_count[j] <= 1:\n",
    "                            new_leaf.add(j)\n",
    "                            grep_count.pop(j)\n",
    "            leaf = new_leaf\n",
    "        return list(leaf)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: \n",
    "        G = defaultdict(list)\n",
    "        for edge in edges:\n",
    "            G[edge[0]].append(edge[1]) \n",
    "            G[edge[1]].append(edge[0]) \n",
    "        if len(G) == 0:\n",
    "            return [0]\n",
    "\n",
    "        def bfs(st, pars):\n",
    "            vis = set()\n",
    "            q = collections.deque()\n",
    "            q.append((st, 0))\n",
    "            end = st\n",
    "            vis.add(st)\n",
    "\n",
    "            while len(q) > 0:\n",
    "                u, dep = q.popleft()\n",
    "                end = u\n",
    "                for v in G[u]:\n",
    "                    if v not in vis:\n",
    "                        vis.add(v)\n",
    "                        pars[v] = u\n",
    "                        q.append((v, dep + 1))\n",
    "            return end\n",
    "\n",
    "        def dfs(st, end):\n",
    "            vis_dfs.add(st)\n",
    "            if st == end:\n",
    "                all_paths.append(copy.copy(path))\n",
    "                return\n",
    "            for v in G[st]:\n",
    "                if v not in vis_dfs:\n",
    "                    path.append(v)\n",
    "                    dfs(v, end)\n",
    "                    path.pop()\n",
    "\n",
    "        # 先用两遍bfs找树的直径\n",
    "        pars = [0] * len(G)\n",
    "        pars[0] = -1\n",
    "        end1 = bfs(0, pars)\n",
    "        pars = [0] * len(G)\n",
    "        pars[end1] = -1\n",
    "        end2 = bfs(end1, pars)\n",
    "\n",
    "        pa = end2\n",
    "        line = []\n",
    "        while pa != -1:\n",
    "            line.append(pa)\n",
    "            pa = pars[pa]\n",
    "\n",
    "        # dfs找到直径对应的路径, 指定起点的dfs\n",
    "        # path = [end1]\n",
    "        # all_paths = []\n",
    "        # vis_dfs = set()\n",
    "        # dfs(end1, end2)\n",
    "        # line = all_paths[0]\n",
    "\n",
    "        res = []\n",
    "        res.append(line[ len(line) // 2])\n",
    "        if len(line) % 2 == 0:\n",
    "            res.append(line[ len(line )// 2 - 1])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        graph = defaultdict(dict)\n",
    "        #construct graph\n",
    "        for edge in edges:\n",
    "            if edge[0] in graph:\n",
    "                graph[edge[0]]['neibors'].append(edge[1])\n",
    "                graph[edge[0]]['indegree'] += 1\n",
    "            else:\n",
    "                graph[edge[0]]['neibors']= [edge[1]]\n",
    "                graph[edge[0]]['indegree'] = 1\n",
    "            if edge[1] in graph:\n",
    "                graph[edge[1]]['neibors'].append(edge[0])\n",
    "                graph[edge[1]]['indegree'] += 1\n",
    "            else:\n",
    "                graph[edge[1]]['neibors']= [edge[0]]\n",
    "                graph[edge[1]]['indegree'] = 1\n",
    "        \n",
    "        queue = deque() \n",
    "        visited = set() \n",
    "        n_removed = 0 \n",
    "\n",
    "        for i in range(n):\n",
    "            if graph[i]['indegree'] == 1:\n",
    "                queue.append(i)\n",
    "                visited.add(i)\n",
    "        \n",
    "        while n - n_removed > 2:\n",
    "            q_size = len(queue)\n",
    "            for i in range(q_size):\n",
    "                cur = queue.popleft() \n",
    "                for nei in graph[cur]['neibors']:\n",
    "                    graph[nei]['indegree'] -= 1 \n",
    "                    if nei not in visited and graph[nei]['indegree'] <= 1:\n",
    "                        queue.append(nei)\n",
    "                        visited.add(nei)\n",
    "                n_removed += 1 \n",
    "        return list(queue)\n",
    "\n",
    "        \n",
    "\n",
    "             \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1: return [0]\n",
    "        graph = {i : set() for i in range(n)}\n",
    "        deg = [0 for i in range(n)]\n",
    "        for ei, ej in edges:\n",
    "            deg[ei] += 1\n",
    "            deg[ej] += 1\n",
    "            graph[ei].add(ej)\n",
    "            graph[ej].add(ei)\n",
    "        queue = collections.deque([])\n",
    "        visited = set()\n",
    "        for i in range(n):\n",
    "            if deg[i] == 1:\n",
    "                queue.append(i)\n",
    "                deg[i] -= 1\n",
    "                visited.add(i)\n",
    "        res = []\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            cur = []\n",
    "            for _ in range(size):\n",
    "                curnode = queue.popleft()\n",
    "                cur.append(curnode)\n",
    "                for nxtnode in graph[curnode]:\n",
    "                    if nxtnode not in visited:\n",
    "                        deg[nxtnode] -= 1\n",
    "                        if deg[nxtnode] == 1:\n",
    "                            queue.append(nxtnode)\n",
    "                            visited.add(nxtnode)\n",
    "            res = cur\n",
    "        return res \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n==1:\n",
    "            return [0]\n",
    "        rem_dict = dict()\n",
    "        for i in edges:\n",
    "            if i[0] in rem_dict:\n",
    "                rem_dict[i[0]].append(i[1])\n",
    "            else:\n",
    "                rem_dict[i[0]] = [i[1]]\n",
    "\n",
    "            if i[1] in rem_dict:\n",
    "                rem_dict[i[1]].append(i[0])\n",
    "            else:\n",
    "                rem_dict[i[1]] = [i[0]]\n",
    "\n",
    "        r = set()\n",
    "        parent = [0] * n\n",
    "\n",
    "        def bfs(index):\n",
    "            r.add(index)\n",
    "            high = 0\n",
    "            current = [index]\n",
    "            end = index\n",
    "            while len(current) > 0:\n",
    "                new = []\n",
    "                for i in current:\n",
    "                    for j in rem_dict[i]:\n",
    "                        if j not in r:\n",
    "                            r.add(j)\n",
    "                            parent[j] = i\n",
    "                            new.append(j)\n",
    "                            end = j\n",
    "                high += 1\n",
    "                current = new\n",
    "\n",
    "            return end\n",
    "\n",
    "        res = None\n",
    "\n",
    "        def dfs(index, target, path=[]):\n",
    "            print(path)\n",
    "            nonlocal res\n",
    "\n",
    "            nodes = [index]\n",
    "            while len(nodes) > 0:\n",
    "                node = nodes.pop()\n",
    "                if node == target:\n",
    "                    return path + [node]\n",
    "                for i in rem_dict[node]:\n",
    "                    if i in path:\n",
    "                        continue\n",
    "\n",
    "                    dfs(i, target, path + [i])\n",
    "\n",
    "        r = set()\n",
    "        left_end = bfs(0)\n",
    "        r = set()\n",
    "        right_end = bfs(left_end)\n",
    "\n",
    "        path = [right_end]\n",
    "        while right_end != left_end:\n",
    "            right_end = parent[right_end]\n",
    "            path.append(right_end)\n",
    "        # dfs(left_end, right_end, [left_end])\n",
    "\n",
    "        if len(path) % 2 == 0:\n",
    "            return [path[len(path) // 2], path[len(path) // 2 - 1]]\n",
    "        else:\n",
    "            return [path[len(path) // 2]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        d = collections.defaultdict(set)\n",
    "        \n",
    "        for root, node in edges:\n",
    "            d[root].add(node)\n",
    "            d[node].add(root)\n",
    "\n",
    "        s = set(range(n))\n",
    "        while len(s) > 2:\n",
    "\n",
    "            leaves = set(i for i in s if len(d[i]) == 1)\n",
    "            s -= leaves\n",
    "\n",
    "\n",
    "            for i in leaves:\n",
    "                for j in d[i]:\n",
    "                    d[j].remove(i)\n",
    "        return list(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        d = collections.defaultdict(set)\n",
    "        # 构建双向映射\n",
    "        for root, node in edges:\n",
    "            d[root].add(node)\n",
    "            d[node].add(root)\n",
    "\n",
    "        s = set(range(n))\n",
    "        while len(s) > 2:\n",
    "            # 去除只出现一次的叶子结点\n",
    "            leaves = set(i for i in s if len(d[i]) == 1)\n",
    "            s -= leaves\n",
    "\n",
    "            # 在映射里面去除只出现一次的叶子结点\n",
    "            for i in leaves:\n",
    "                for j in d[i]:\n",
    "                    d[j].remove(i)\n",
    "        return list(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees_overtime(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        link=collections.defaultdict(list)\n",
    "        num=collections.defaultdict(int)\n",
    "\n",
    "        for edge in edges:\n",
    "            link[edge[0]].append(edge[1])\n",
    "            link[edge[1]].append(edge[0])\n",
    "            num[edge[0]]+=1\n",
    "            num[edge[1]]+=1\n",
    "        rankednum=sorted(num.items(),key=lambda d:d[1],reverse=True)\n",
    "        print(rankednum)\n",
    "        \n",
    "\n",
    "        def h(st):\n",
    "            q=collections.deque()\n",
    "            q.append([st,0])\n",
    "            visited=[0]*n\n",
    "            visited[st]=1\n",
    "\n",
    "            while q:\n",
    "                u,len_=q.popleft()\n",
    "                for v in link[u]:\n",
    "                    if visited[v]==0:\n",
    "                        visited[v]=1\n",
    "                        q.append([v,len_+1])\n",
    "            return len_\n",
    "\n",
    "        min_h=n\n",
    "        res=[]\n",
    "        for u in rankednum:\n",
    "            tmp=h(u[0])\n",
    "            #print(u[0],tmp)\n",
    "            if tmp<min_h:\n",
    "                min_h=tmp\n",
    "                res=[]\n",
    "                res.append(u[0])\n",
    "            elif tmp==min_h:\n",
    "                res.append(u[0])\n",
    "            #print(u[0],res)\n",
    "        if res==[]:\n",
    "            return [0]\n",
    "        return res\n",
    "    def findMinHeightTrees1(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n==1:\n",
    "            return [0]\n",
    "        link=collections.defaultdict(list)\n",
    "        indeg=collections.defaultdict(int)\n",
    "\n",
    "        for edge in edges:\n",
    "            link[edge[0]].append(edge[1])\n",
    "            link[edge[1]].append(edge[0])\n",
    "            indeg[edge[0]]+=1\n",
    "            indeg[edge[1]]+=1\n",
    "        \n",
    "        q=[u for u in range(n) if indeg[u]==1]\n",
    "        remainNodes=n\n",
    "        while remainNodes>2:\n",
    "            remainNodes-=len(q)\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for x in tmp:\n",
    "                for y in link[x]:\n",
    "                    indeg[y]-=1\n",
    "                    if indeg[y]==1:\n",
    "                        q.append(y)\n",
    "        return q\n",
    "    def findMinHeightTrees2(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n==1:\n",
    "            return [0]\n",
    "        if n==2:\n",
    "            return [0,1]\n",
    "        e=defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "        q=deque()\n",
    "        for key,val in e.items():\n",
    "            if len(val)==1:\n",
    "                q.append(key)\n",
    "        while q:\n",
    "            len_=len(q)\n",
    "            n=n-len_\n",
    "            for _ in range(len_):\n",
    "                v=q.popleft()\n",
    "                v_adj=e[v].pop()\n",
    "                e[v_adj].remove(v)\n",
    "                if len(e[v_adj])==1:\n",
    "                    q.append(v_adj)\n",
    "            if n==1:\n",
    "                return [q.popleft()]\n",
    "            if n==2:\n",
    "                return [q.popleft(),q.popleft()]\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        e=defaultdict(set)\n",
    "        for root,node in edges:\n",
    "            e[root].add(node)\n",
    "            e[node].add(root)\n",
    "\n",
    "        s=set(range(n))\n",
    "        while len(s)>2:\n",
    "            leaves=set(i for i in s if len(e[i])==1)\n",
    "            s-=leaves\n",
    "\n",
    "            for i in leaves:\n",
    "                for j in e[i]:\n",
    "                    e[j].remove(i)\n",
    "        return list(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        d = collections.defaultdict(set)\n",
    "        # 双向映射\n",
    "        for root, node in edges:\n",
    "            d[root].add(node)\n",
    "            d[node].add(root)\n",
    "        print(d)\n",
    "        s = set(range(n))\n",
    "        while len(s) > 2:\n",
    "            # 去掉只出现一次的叶子节点\n",
    "            leaves = set(i for i in s if len(d[i]) == 1)\n",
    "            s -= leaves\n",
    "\n",
    "            # 去掉在映射中只出现一次的叶子结点\n",
    "            for i in leaves:\n",
    "                for j in d[i]:\n",
    "                    d[j].remove(i)\n",
    "        return list(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = dict()\n",
    "        for i in range(n):\n",
    "            graph[i] = set()\n",
    "        for i, j in edges:\n",
    "            graph[i].add(j)\n",
    "            graph[j].add(i)\n",
    "        leaf = set()\n",
    "        for i in range(n):\n",
    "            if len(graph[i]) <= 1:\n",
    "                leaf.add(i)\n",
    "        node = set(range(n))\n",
    "        node = node.difference(leaf)\n",
    "        # print(leaf)\n",
    "        while len(node) > 0:\n",
    "            new_leaf = set()\n",
    "            for i in leaf:\n",
    "                if len(graph[i]) == 0:\n",
    "                    continue\n",
    "                j = graph[i].pop()\n",
    "                graph[j].remove(i)\n",
    "                if len(graph[j]) <= 1:\n",
    "                    new_leaf.add(j)\n",
    "            leaf = new_leaf\n",
    "            # print(leaf)\n",
    "            node = node.difference(leaf)\n",
    "        return list(leaf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1:return [0]\n",
    "        g = {i:set() for i in range(n)}\n",
    "        node = set(range(n))\n",
    "        for x,y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        leaves = {i for i in range(n) if len(g[i])==1}\n",
    "        while node != leaves:\n",
    "            node -= leaves\n",
    "            newleaf = set()\n",
    "            for leaf in leaves:\n",
    "                root = g[leaf].pop()\n",
    "                g[root].remove(leaf)\n",
    "                if len(g[root])==1:\n",
    "                    newleaf.add(root)\n",
    "            leaves = newleaf\n",
    "        return list(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        edgeDict=collections.defaultdict(list)\n",
    "        degreeDict=collections.defaultdict(int)\n",
    "        reverseDict=collections.defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            edgeDict[u].append(v)\n",
    "            edgeDict[v].append(u)\n",
    "        for u in range(n):\n",
    "            s=len(edgeDict[u])\n",
    "            degreeDict[u]=s \n",
    "            reverseDict[s].add(u)\n",
    "        remove_list=set()\n",
    "        while len(remove_list)+len(reverseDict[1])+len(reverseDict[0])<n:\n",
    "            #print(reverseDict,remove_list)\n",
    "            temp=set()\n",
    "            for u in reverseDict[1]:\n",
    "                temp.add(u)\n",
    "                remove_list.add(u)\n",
    "            del reverseDict[1]\n",
    "            for u in temp:\n",
    "                for v in edgeDict[u]:\n",
    "                    if v not in remove_list:\n",
    "                        reverseDict[degreeDict[v]].remove(v)\n",
    "                        degreeDict[v]-=1\n",
    "                        reverseDict[degreeDict[v]].add(v)\n",
    "        return list(reverseDict[1])+list(reverseDict[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        q = deque([0])\n",
    "        seen = set([0])\n",
    "        node = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                for neighbor in graph[node]:\n",
    "                    if neighbor not in seen:\n",
    "                        seen.add(neighbor)\n",
    "                        q.append(neighbor)\n",
    "        x = node\n",
    "        seen.clear()\n",
    "        q = deque([(x, [x])])\n",
    "        seen.add(x)\n",
    "        path = [x]\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                node, path = q.popleft()\n",
    "                for neighbor in graph[node]:\n",
    "                    if neighbor not in seen:\n",
    "                        seen.add(neighbor)\n",
    "                        q.append((neighbor, path+[neighbor]))\n",
    "       \n",
    "        if len(path) % 2 == 0:\n",
    "        \n",
    "            return [path[len(path)//2-1], path[len(path)//2]]\n",
    "        else:\n",
    "            return [path[len(path)//2]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n==1:\n",
    "            return [0]\n",
    "        d={}\n",
    "        for i in range(n):\n",
    "            d[i]=[]\n",
    "        for i in range(len(edges)):\n",
    "            a,b=edges[i][0],edges[i][1]\n",
    "            d[a].append(b)\n",
    "            d[b].append(a)\n",
    "        mini=100000000\n",
    "        xmin=[]\n",
    "        x=deque([0])\n",
    "        index=[0 for k in range(n)]\n",
    "        index[0]=1\n",
    "        maxi=0\n",
    "        p=0\n",
    "        while(len(x)):\n",
    "            x0=x.popleft()\n",
    "            p=x0\n",
    "            for k in range(len(d[x0])):\n",
    "                if index[d[x0][k]]==0:\n",
    "                    index[d[x0][k]]=1\n",
    "                    x.append(d[x0][k])\n",
    "        x=deque([[p,0,[p]]])\n",
    "        index=[0 for k in range(n)]\n",
    "        index[p]=1\n",
    "        maxi=0\n",
    "        p=[]\n",
    "        while(len(x)):\n",
    "            x0=x.popleft()\n",
    "            a,b=x0[0],x0[1]\n",
    "            if b>maxi:\n",
    "                maxi=b\n",
    "                p=x0[-1]\n",
    "            for k in range(len(d[a])):\n",
    "                if index[d[a][k]]==0:\n",
    "                    index[d[a][k]]=1\n",
    "                    x.append([d[a][k],b+1,x0[-1]+[d[a][k]]])\n",
    "        #print(p)\n",
    "        x=len(p)//2\n",
    "\n",
    "        if len(p)%2==1:\n",
    "            return [p[x]]\n",
    "        return [p[x-1],p[x]]\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import  collections\n",
    "import sys\n",
    "from typing import List\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        e = collections.defaultdict(set)        #字典初始化为集合\n",
    "        for i, j in edges:\n",
    "            e[i] |= {j}    #set集合的并集操作，右边并进左边的集合                     #把边哈希化，方便调用\n",
    "            e[j] |= {i}\n",
    "        q = {i for i in e if len(e[i]) == 1}    #建立初始宽搜队列，长度为1时代表只连接一个点\n",
    "        while n > 2:\n",
    "            t = set()                   #临时队列\n",
    "            for i in q:\n",
    "                j = e[i].pop()          #把连接点取出\n",
    "                e[j] -= {i}             #连接是双向的，所以要删除关系\n",
    "                if len(e[j]) == 1:      #更新后，如果长度为1时则加入下一个轮队列\n",
    "                    t |= {j}\n",
    "                n -= 1                  #删除计数\n",
    "            q = t\n",
    "        return list(q)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        neighbor = {a: [] for a in range(n)}\n",
    "        for a, b in edges:\n",
    "            neighbor[a].append(b)\n",
    "            neighbor[b].append(a)\n",
    "        def longestPath(node):\n",
    "            queue = [(node, [node])]\n",
    "            visited = {node}\n",
    "            while queue:\n",
    "                node, path = queue.pop(0)\n",
    "                for nei in neighbor[node]:\n",
    "                    if nei not in visited:\n",
    "                        queue.append((nei, path+[nei]))\n",
    "                        visited.add(nei)\n",
    "            return node, path\n",
    "        x, path = longestPath(0)\n",
    "        y, path = longestPath(x)\n",
    "        length = len(path)\n",
    "        return path[length//2 : length//2+1] if length % 2 == 1 else path[length//2-1 : length//2+1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        recordS = {}\n",
    "        for i in range(n):\n",
    "            recordS[i] = []\n",
    "        for i in edges:\n",
    "            recordS[i[0]].append(i[1])\n",
    "            recordS[i[1]].append(i[0])\n",
    "        for i, j in recordS.items():\n",
    "            if len(j) == 1:\n",
    "                break\n",
    "        record = copy.deepcopy(recordS)\n",
    "        path = [[i]]\n",
    "        maxlen = 1\n",
    "        height = 1\n",
    "        while True:\n",
    "            layer = []\n",
    "            for i in path:\n",
    "                temp = []\n",
    "                for j in recordS[i[-1]]:\n",
    "                    temp.append(i + [j])\n",
    "                    recordS[j].remove(i[-1])\n",
    "                layer += temp\n",
    "            if not layer: break\n",
    "            path = layer\n",
    "            height += 1\n",
    "        path = [[path[0][-1]]]\n",
    "        maxlen = 1\n",
    "        height = 1\n",
    "        while True:\n",
    "            layer = []\n",
    "            for i in path:\n",
    "                temp = []\n",
    "                for j in record[i[-1]]:\n",
    "                    temp.append(i + [j])\n",
    "                    record[j].remove(i[-1])\n",
    "                layer += temp\n",
    "            if not layer: break\n",
    "            path = layer\n",
    "            height += 1\n",
    "\n",
    "        if len(path[-1]) % 2:\n",
    "            return [path[0][len(path[0]) // 2]]\n",
    "        return [path[0][len(path[0]) // 2], path[0][len(path[0]) // 2 - 1]]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        @cache\n",
    "        def far(root, father):\n",
    "            ways = [far(son, root) for son in g[root] if son != father]\n",
    "            if not ways:\n",
    "                return 0\n",
    "            return max(ways)+1\n",
    "        total = list((i, far(i, -1)) for i in range(n))\n",
    "        print(total)\n",
    "        target = min(total, key=lambda x:x[-1])[-1]\n",
    "        res = [i for i, val in total if val == target]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    # def check_leave(self,matrix):\n",
    "    #     return [idx_ for idx_,i in enumerate(np.sum(matrix,axis=1)) if i==1]\n",
    "\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        #构建邻接矩阵\n",
    "        degree = np.zeros(shape=(n))\n",
    "        node_map = {}\n",
    "        for i in edges:\n",
    "            degree[i[0]] += 1\n",
    "            degree[i[1]] += 1\n",
    "            if i[0] not in node_map:\n",
    "                node_map[i[0]] = [i[1]]\n",
    "            else:\n",
    "                node_map[i[0]] += [i[1]]\n",
    "            if i[1] not in node_map:\n",
    "                node_map[i[1]] = [i[0]]\n",
    "            else:\n",
    "                node_map[i[1]] += [i[0]]\n",
    "\n",
    "        leave_list = [idx_ for idx_,i in enumerate(degree) if i==1]\n",
    "        last_leave = leave_list\n",
    "        while leave_list:\n",
    "            last_leave = leave_list.copy()\n",
    "            tmp_leave_list = []\n",
    "            while leave_list:\n",
    "                leave = leave_list.pop()\n",
    "                ner_list = node_map[leave]\n",
    "                while ner_list:\n",
    "                    ner = ner_list.pop()\n",
    "                    degree[ner] -= 1\n",
    "                    if(degree[ner] == 1):\n",
    "                        tmp_leave_list = [ner] + tmp_leave_list\n",
    "            leave_list = tmp_leave_list\n",
    "            if len(leave_list)>0:\n",
    "                last_leave = leave_list.copy()\n",
    "\n",
    "        return last_leave"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = []\n",
    "        self.state = []\n",
    "\n",
    "    def findMinHeightTrees(self, n: int, edges: list) -> list:\n",
    "        # 链式前向星存储图结构\n",
    "        self._init_Variable(n, edges)\n",
    "        self.DFS1(0, -1)\n",
    "        self.DFS2(0, -1)\n",
    "\n",
    "        # print(self.f1, self.f2)\n",
    "        min_height = float('inf')\n",
    "        for id in range(n):\n",
    "            cur = max(self.f1[id], self.g[id])\n",
    "            if cur == min_height:\n",
    "                self.ans.append(id)\n",
    "            elif cur < min_height:\n",
    "                self.ans.clear()\n",
    "                self.ans.append(id)\n",
    "                min_height = cur\n",
    "\n",
    "\n",
    "        return self.ans\n",
    "\n",
    "    def _init_Variable(self, n: int, edges: list):\n",
    "        self.head, self.tail, self.next = [-1 for _ in range(n)], [], []\n",
    "        self.f1 = [0 for _ in range(n)]\n",
    "        self.f2 = [0 for _ in range(n)]\n",
    "        self.g = [0 for _ in range(n)]\n",
    "        self.p = [-1 for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            self.add(x, y)\n",
    "            self.add(y, x)\n",
    "\n",
    "    def add(self, a, b):\n",
    "        self.tail.append(b)\n",
    "        self.next.append(self.head[a])\n",
    "        self.head[a] = len(self.tail) - 1\n",
    "\n",
    "\n",
    "    def DFS1(self, root, Prenode):\n",
    "        now_edge = self.head[root]\n",
    "        while now_edge != -1:\n",
    "            tail = self.tail[now_edge]\n",
    "            if tail == Prenode:\n",
    "                now_edge = self.next[now_edge]\n",
    "                continue\n",
    "\n",
    "            now_depth = self.DFS1(tail, root) + 1\n",
    "            if now_depth > self.f1[root]:\n",
    "                self.f2[root] = self.f1[root]\n",
    "                self.f1[root] = now_depth\n",
    "                self.p[root] = tail\n",
    "            elif now_depth > self.f2[root]:\n",
    "                self.f2[root] = now_depth\n",
    "\n",
    "            now_edge = self.next[now_edge]\n",
    "\n",
    "        return self.f1[root]\n",
    "\n",
    "    def DFS2(self, root, Prenode):\n",
    "        now_edge = self.head[root]\n",
    "\n",
    "        while now_edge != -1:\n",
    "            tail = self.tail[now_edge]\n",
    "            if tail == Prenode:\n",
    "                now_edge = self.next[now_edge]\n",
    "                continue\n",
    "\n",
    "            if self.p[root] != tail: self.g[tail] = max(self.g[tail],self.f1[root] + 1)\n",
    "            else: self.g[tail] = max(self.g[tail], self.f2[root] + 1)\n",
    "\n",
    "            # print(tail, self.g[tail], self.f1[root], self.f2[root], self.g[root])\n",
    "\n",
    "            self.g[tail] = max(self.g[tail], self.g[root] + 1)\n",
    "\n",
    "            self.DFS2(tail, root)\n",
    "\n",
    "            now_edge = self.next[now_edge]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1: return [0]\n",
    "        self.n = n\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        self.maxDepth, self.node = 0, -1\n",
    "        self.parent = [0] * n\n",
    "        self.dfs(graph, 0, -1, 1)\n",
    "        self.maxDepth = 0\n",
    "        self.dfs(graph, self.node, -1, 1)\n",
    "        path = []\n",
    "        while self.node != -1:\n",
    "            path.append(self.node)\n",
    "            self.node = self.parent[self.node]\n",
    "        m = len(path)\n",
    "        return [path[m // 2]] if m % 2 else [path[m // 2 - 1], path[m // 2]]\n",
    "    \n",
    "    def dfs(self, graph, node, p, depth):\n",
    "        if depth > self.maxDepth:\n",
    "            self.maxDepth, self.node = depth, node\n",
    "        self.parent[node] = p\n",
    "        for neighbor in graph[node]:\n",
    "            if neighbor != p:\n",
    "                self.dfs(graph, neighbor, node, depth + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        # bfs + 回溯\n",
    "\n",
    "        # 注意到树中的最小高度树的数量只能为1，2，如果树高为奇数则1个，否则为2个\n",
    "        # 依照题意，每个节点都可以作为根节点，即目标是找到这样的节点，使该节点作为根节点时，树的高度最小\n",
    "        # 该问题可以转化为寻找任意节点为根节点的最长路长度，将最长树的中间位置的节点(1或2个)作为根节点就能获得最小高度树\n",
    "        # 该机制的正确性可以使用反证法来证明\n",
    "\n",
    "        # 如何寻找最长路？\n",
    "        # 以任意一个节点为根节点，得到的树中的最深的节点必定是最长路的端点之一\n",
    "        # 不妨以0为根节点\n",
    "        # 使用bfs搜索路的终点\n",
    "        if n == 1:return [0]\n",
    "        neig = defaultdict(list)\n",
    "        for e in edges:\n",
    "            i,j = e\n",
    "            neig[i].append(j)\n",
    "            neig[j].append(i)\n",
    "        node_set = [0]\n",
    "        visit = [False]*n\n",
    "        visit[0] = True\n",
    "        end_node = 0\n",
    "        while node_set:\n",
    "            node = node_set.pop(0)\n",
    "            end_node = node\n",
    "            for no in neig[node]:\n",
    "                if not visit[no]:\n",
    "                    visit[no] = True\n",
    "                    node_set.append(no)\n",
    "        # 得到的endnode就是终点\n",
    "\n",
    "        # 再对endnode使用一次回溯确定路径\n",
    "        global max_len,ans\n",
    "        max_len,route,ans = 1,[end_node],[]\n",
    "        visit = [False]*n\n",
    "        visit[end_node] = True\n",
    "        backtrack(route,1,neig,visit)\n",
    "        if max_len%2:\n",
    "            return [ans[max_len//2]]\n",
    "        return [ans[max_len//2],ans[max_len//2-1]]\n",
    "\n",
    "def backtrack(route,length,neig,visit):\n",
    "    exist = False\n",
    "    for n in neig[route[-1]]:\n",
    "        if not visit[n]:\n",
    "            visit[n] = True\n",
    "            route.append(n)\n",
    "            backtrack(route,length+1,neig,visit)\n",
    "            route.pop(-1)\n",
    "            visit[n] = False\n",
    "            exist = True\n",
    "    if not exist:\n",
    "        global max_len, ans\n",
    "        if length>max_len:\n",
    "            max_len = length\n",
    "            ans = route[::]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 注意到树中的最小高度树的数量只能为1，2，如果树高为奇数则1个，否则为2个\n",
    "        # 依照题意，每个节点都可以作为根节点，即目标是找到这样的节点，使该节点作为根节点时，树的高度最小\n",
    "        # 该问题可以转化为寻找任意节点为根节点的最长路长度，将最长树的中间位置的节点(1或2个)作为根节点就能获得最小高度树\n",
    "        # 该机制的正确性可以使用反证法来证明\n",
    "\n",
    "        # 如何寻找最长路？\n",
    "        # 以任意一个节点为根节点，得到的树中的最深的节点必定是最长路的端点之一\n",
    "        # 不妨以0为根节点\n",
    "        # 使用bfs搜索路的终点\n",
    "        if n == 1:return [0]\n",
    "        neig = defaultdict(list)\n",
    "        for e in edges:\n",
    "            i,j = e\n",
    "            neig[i].append(j)\n",
    "            neig[j].append(i)\n",
    "        node_set = [0]\n",
    "        visit = [False]*n\n",
    "        visit[0] = True\n",
    "        end_node = 0\n",
    "        while node_set:\n",
    "            node = node_set.pop(0)\n",
    "            end_node = node\n",
    "            for no in neig[node]:\n",
    "                if not visit[no]:\n",
    "                    visit[no] = True\n",
    "                    node_set.append(no)\n",
    "        # 得到的endnode就是终点\n",
    "\n",
    "        # 再对endnode使用一次回溯确定路径\n",
    "        global max_len,ans\n",
    "        max_len,ans = 1,[]\n",
    "        max_len,route,ans = 1,[end_node],[]\n",
    "        visit = [False]*n\n",
    "        visit[end_node] = True\n",
    "        backtrack(route,1,neig,visit)\n",
    "        if max_len%2:\n",
    "            return [ans[max_len//2]]\n",
    "        return [ans[max_len//2],ans[max_len//2-1]]\n",
    "\n",
    "def backtrack(route,length,neig,visit):\n",
    "    exist = False\n",
    "    for n in neig[route[-1]]:\n",
    "        if not visit[n]:\n",
    "            visit[n] = True\n",
    "            route.append(n)\n",
    "            backtrack(route,length+1,neig,visit)\n",
    "            route.pop(-1)\n",
    "            visit[n] = False\n",
    "            exist = True\n",
    "    if not exist:\n",
    "        global max_len, ans\n",
    "        if length>max_len:\n",
    "            max_len = length\n",
    "            ans = route[::]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        self.con = defaultdict(list)\n",
    "        self.f1 = [0 for x in range(n)]\n",
    "        self.f2 = [0 for x in range(n)]\n",
    "        self.g = [0 for x in range(n)]\n",
    "        self.p = [0 for x in range(n)]\n",
    "\n",
    "        for edge in edges:\n",
    "            self.con[edge[0]].append(edge[1])\n",
    "            self.con[edge[1]].append(edge[0])\n",
    "\n",
    "        self.dfs1(0, -1)\n",
    "        self.dfs2(0, -1)\n",
    "\n",
    "        hs = [max(x, y) for (x,y) in zip(self.f1, self.g)]\n",
    "        \n",
    "        l = min(hs)\n",
    "        return [i for (i, x) in enumerate(hs) if x == l]\n",
    "\n",
    "\n",
    "\n",
    "    def dfs1(self, cur, pre):\n",
    "        for node in self.con[cur]:\n",
    "            if node == pre:\n",
    "                continue\n",
    "            l = self.dfs1(node, cur) + 1\n",
    "            if l > self.f1[cur]:\n",
    "                self.p[cur] = node\n",
    "                self.f2[cur] = self.f1[cur]\n",
    "                self.f1[cur] = l\n",
    "            elif l > self.f2[cur]:\n",
    "                self.f2[cur] = l\n",
    "        \n",
    "        return self.f1[cur]\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "    def dfs2(self, cur, pre):\n",
    "        for node in self.con[cur]:\n",
    "            if node == pre:\n",
    "                continue\n",
    "            if self.p[cur] != node:\n",
    "                self.g[node] = self.f1[cur] + 1\n",
    "            else:\n",
    "                self.g[node] = self.f2[cur] + 1\n",
    "            \n",
    "            self.g[node] = max(self.g[node], self.g[cur]+1)\n",
    "            self.dfs2(node, cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # #topology sort\n",
    "    # def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "    #     from collections import deque\n",
    "    #     if n == 1:\n",
    "    #         return [0]\n",
    "    #     graph = [[] for _ in range(n)]\n",
    "    #     degree = [0] * n\n",
    "    #     for u, v in edges:\n",
    "    #         graph[u].append(v)\n",
    "    #         graph[v].append(u)\n",
    "    #         degree[u] += 1\n",
    "    #         degree[v] += 1\n",
    "    #     queue = deque()\n",
    "    #     visited = set()\n",
    "    #     for i in range(n):\n",
    "    #         if degree[i] == 1:\n",
    "    #             queue.append(i)\n",
    "    #             visited.add(i)\n",
    "    #     res = []\n",
    "    #     while queue:\n",
    "    #         res = []\n",
    "    #         size = len(queue)\n",
    "    #         for _ in range(size):\n",
    "    #             u = queue.popleft()\n",
    "    #             res.append(u)\n",
    "    #             for v in graph[u]:\n",
    "    #                 if v in visited:\n",
    "    #                     continue\n",
    "    #                 degree[v] -= 1\n",
    "    #                 if degree[v] == 1:\n",
    "    #                     queue.append(v)\n",
    "    #                     visited.add(v)\n",
    "    #     return res\n",
    "\n",
    "    #BFS/DFS\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        from collections import deque\n",
    "        graph = [[] for _ in range(n)]\n",
    "        parents = [-1] * n\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        def bfs(root):\n",
    "            res = None\n",
    "            queue = deque()\n",
    "            queue.append(root)\n",
    "            parents[root] = -1\n",
    "            while queue:\n",
    "                u  = queue.popleft()\n",
    "                res = u\n",
    "                for v in graph[u]:\n",
    "                    if v != parents[u]:\n",
    "                        parents[v] = u\n",
    "                        queue.append(v)\n",
    "            return res\n",
    "        def dfs(root):\n",
    "            max_dis = 0\n",
    "            parents[root] = -1\n",
    "            res = root\n",
    "            def helper(u, dis):\n",
    "                nonlocal max_dis, res\n",
    "                if max_dis < dis:\n",
    "                    max_dis = dis\n",
    "                    res = u\n",
    "                for v in graph[u]:\n",
    "                    if v != parents[u]:\n",
    "                        parents[v] = u\n",
    "                        helper(v, dis+1)\n",
    "            helper(root, 0)\n",
    "            return res\n",
    "\n",
    "        x = dfs(0)\n",
    "        y = dfs(x)\n",
    "        nodes = []\n",
    "        while y != -1:\n",
    "            nodes.append(y)\n",
    "            y = parents[y]\n",
    "        if len(nodes) % 2:\n",
    "            return [nodes[len(nodes) // 2]]\n",
    "        else:\n",
    "            return [nodes[len(nodes) // 2 - 1], nodes[len(nodes) // 2]]\n",
    "\n",
    "    # #DP\n",
    "    # def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 最长路径的中点\n",
    "\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        pre = [-1] * n\n",
    "\n",
    "        def dfs(u, p, depth):\n",
    "            ret = (u, depth)\n",
    "            pre[u] = p\n",
    "\n",
    "            for v in graph[u]:\n",
    "                if v != p:\n",
    "                    a = dfs(v, u, depth + 1)\n",
    "                    if a[1] > ret[1]:\n",
    "                        ret = a\n",
    "\n",
    "            return ret\n",
    "        \n",
    "        p = dfs(0, 0, 0)\n",
    "        lp = dfs(p[0], p[0], 0)\n",
    "\n",
    "        path = []\n",
    "        node = lp[0]\n",
    "        while pre[node] != node:\n",
    "            path.append(node)\n",
    "            node = pre[node]\n",
    "        path.append(node)\n",
    "\n",
    "        l = len(path)\n",
    "\n",
    "        if l % 2 == 0:\n",
    "            return [path[l // 2 - 1], path[l // 2]]\n",
    "        else:\n",
    "            return [path[l // 2]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ak={}\n",
    "        self.l=[]\n",
    "        self.l_list=[]\n",
    "    def deep(self,root,innode):\n",
    "        self.l.append(root)\n",
    "        if len(self.ak[root])==1 and innode!=-1:\n",
    "            if len(self.l_list)==0 or len(self.l)>len(self.l_list[0]):\n",
    "                self.l_list=[self.l.copy()]\n",
    "            elif len(self.l)==len(self.l_list[0]):\n",
    "                self.l_list.append(self.l.copy())\n",
    "        else:\n",
    "            for i in self.ak[root]:\n",
    "                if i==innode:\n",
    "                    continue\n",
    "                self.deep(i,root)\n",
    "        self.l.pop()\n",
    "\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        for i in edges:\n",
    "            if i[0] not in self.ak:\n",
    "                self.ak[i[0]] = []\n",
    "            if i[1] not in self.ak:\n",
    "                self.ak[i[1]] = []\n",
    "\n",
    "            self.ak[i[0]].append(i[1])\n",
    "            self.ak[i[1]].append(i[0])\n",
    "        if len(edges)==0:\n",
    "            return [0]\n",
    "        for i in self.ak:\n",
    "            if len(self.ak[i])==1:\n",
    "                self.deep(i,-1)\n",
    "                break\n",
    "        self.deep(self.l_list[0][-1],-1)\n",
    "        print(self.l_list)\n",
    "        ans_set = set()\n",
    "        odd = (len(self.l_list[0])%2==1)\n",
    "        for i in self.l_list:\n",
    "            if odd:\n",
    "                ans_set.add(i[len(i)//2])\n",
    "            else:\n",
    "                ans_set.add(i[len(i)//2])\n",
    "                ans_set.add(i[len(i)//2-1])\n",
    "        return list(ans_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n, edges):\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "\n",
    "        neibs_dict = {}\n",
    "        for node1, node2 in edges:\n",
    "            neibs1 = neibs_dict.get(node1, [])\n",
    "            neibs1.append(node2)\n",
    "            neibs_dict[node1] = neibs1\n",
    "\n",
    "            neibs2 = neibs_dict.get(node2, [])\n",
    "            neibs2.append(node1)\n",
    "            neibs_dict[node2] = neibs2\n",
    "\n",
    "        path_1 = self.get_longest(n, neibs_dict, 0)\n",
    "        path_longest = self.get_longest(n, neibs_dict, path_1[0])\n",
    "        diameter = len(path_longest)\n",
    "        result = []\n",
    "        if diameter % 2 == 0:\n",
    "            result.append(path_longest[int(diameter/2)])\n",
    "            result.append(path_longest[int(diameter/2)-1])\n",
    "        else:\n",
    "            result.append(path_longest[int((diameter-1)/2)])\n",
    "\n",
    "        return result\n",
    "\n",
    "    def get_longest(self, n, neibs_dict, node):\n",
    "        visited = [False] * n\n",
    "\n",
    "        def dfs(cur_node):\n",
    "            if not visited[cur_node]:\n",
    "                visited[cur_node] = True\n",
    "                path = []\n",
    "                for neib in neibs_dict[cur_node]:\n",
    "                    next_path = dfs(neib)\n",
    "                    if next_path is not None and len(next_path) > len(path):\n",
    "                        path = next_path\n",
    "                path.append(cur_node)\n",
    "                return path\n",
    "        return dfs(node)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        G=[[] for i in range(n)]\n",
    "        for u,v in edges:\n",
    "            G[u].append(v)\n",
    "            G[v].append(u)\n",
    "        height0=[0]*n\n",
    "        def dfs1(u,fa):\n",
    "            h=0\n",
    "            for v in G[u]:\n",
    "                if v==fa:\n",
    "                    continue\n",
    "                h=max(h,dfs1(v,u))\n",
    "            height0[u]=h+1\n",
    "            return h+1\n",
    "        \n",
    "        height=[0]*n\n",
    "        def dfs2(u,fa):\n",
    "            d1,d2=0,0\n",
    "            for v in G[u]:\n",
    "                if height0[v]>=d1:\n",
    "                    d2=d1\n",
    "                    d1=height0[v]\n",
    "                elif height0[v]>d2:\n",
    "                    d2=height0[v]\n",
    "            height[u]=d1+1\n",
    "            for v in G[u]:\n",
    "                if v==fa:\n",
    "                    continue\n",
    "                height0[u]=d1+1 if height0[v]!=d1 else d2+1\n",
    "                dfs2(v,u)\n",
    "        dfs1(0,-1)\n",
    "        dfs2(0,-1)\n",
    "        ans=[]\n",
    "        h=float('inf')\n",
    "        for i,v in enumerate(height):\n",
    "            if v>h:\n",
    "                continue\n",
    "            if v<h:\n",
    "                h=v\n",
    "                ans=[]\n",
    "            ans.append(i)\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#可能需要搭配手写栈板子，仅适合1e5及以下数据\n",
    "import bisect\n",
    "class Dfstreemono:\n",
    "    def __init__(self,edges):#顶点数量，边\n",
    "        n = len(edges)+1\n",
    "        self.nums = [[] for _ in range(n)]\n",
    "        for i,j in edges:\n",
    "            self.nums[i].append(j)\n",
    "            self.nums[j].append(i)\n",
    "        for i in range(n):\n",
    "            self.nums[i].sort()\n",
    "        self.presum = [0]*n\n",
    "        self.sufsum = [0]*n\n",
    "        self.has = [{} for _ in range(n)]\n",
    "        self.used = [-1]*n#-1未遍历，-2已经遍历完了，else一个节点未遍历\n",
    "    def build(self,node):\n",
    "        lin = [0]\n",
    "        left = 0\n",
    "        for i in self.nums[node]:\n",
    "            left = max(left, self.has[node][i])\n",
    "            lin.append(left)\n",
    "        self.presum[node] = lin\n",
    "        lin = [0]\n",
    "        right = 0\n",
    "        for i in self.nums[node][::-1]:\n",
    "            right = max(right, self.has[node][i])\n",
    "            lin.append(right)\n",
    "        lin = lin[::-1]\n",
    "        self.sufsum[node] = lin\n",
    "    def dfs(self,node,pre):\n",
    "        res = 0\n",
    "        if self.used[node] == -1:\n",
    "            for i in self.nums[node]:\n",
    "                if i != pre:\n",
    "                    self.has[node][i] = self.dfs(i,node)+1\n",
    "                    res = max(res,self.has[node][i])\n",
    "            if node == pre:\n",
    "                self.build(node)\n",
    "                self.used[node] = -2\n",
    "            else:\n",
    "                self.used[node] = pre\n",
    "        else:\n",
    "            if self.used[node] != -2:\n",
    "                self.has[node][self.used[node]] = self.dfs(self.used[node],node)+1\n",
    "                self.build(node)\n",
    "                self.used[node] = -2\n",
    "            if pre != node:\n",
    "                idx = bisect.bisect_left(self.nums[node],pre)\n",
    "                res = max(self.presum[node][idx], self.sufsum[node][idx + 1])\n",
    "            else:\n",
    "                res = self.sufsum[node][0]\n",
    "        return res\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        dfst = Dfstreemono(edges)\n",
    "        has = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            has[dfst.dfs(i,i)].append(i)\n",
    "        return has[min(has)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        h = [1] * n\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            for y in graph[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "                    h[x] = max(h[x], h[y] + 1)\n",
    "        dfs(0, -1)\n",
    "\n",
    "        def reroot(x: int, fa: int, height: int) -> None:\n",
    "            h[x] = max(h[x], height + 1)\n",
    "            f = height + 1\n",
    "            g = 0\n",
    "            for y in graph[x]:\n",
    "                if y != fa:\n",
    "                    if h[y] + 1 >= f:\n",
    "                        g = f\n",
    "                        f = h[y] + 1\n",
    "                    elif h[y] + 1 >= g:\n",
    "                        g = h[y] + 1\n",
    "            for y in graph[x]:\n",
    "                if y != fa:\n",
    "                    if h[y] + 1 == f:\n",
    "                        reroot(y, x, g)\n",
    "                    else:\n",
    "                        reroot(y, x, f)\n",
    "        reroot(0, -1, 0)\n",
    "        \n",
    "        mn = min(h)\n",
    "        return [i for i in range(n) if h[i] == mn]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        dist1 = [0] * n\n",
    "        dist2 = [0] * n\n",
    "        dist3 = [0] * n\n",
    "\n",
    "        def dfs(x, fa, dist):\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dist[y] = dist[x] + 1\n",
    "                    dfs(y, x, dist)\n",
    "        \n",
    "\n",
    "        dfs(0, -1, dist1)\n",
    "        mx = -inf\n",
    "        for i in range(n):\n",
    "            if dist1[i] > mx:\n",
    "                mx = dist1[i]\n",
    "                j = i\n",
    "        \n",
    "        dfs(j, -1, dist2)\n",
    "        mx = -inf\n",
    "        for i in range(n):\n",
    "            if dist2[i] > mx:\n",
    "                mx = dist2[i]\n",
    "                k = i\n",
    "        \n",
    "        dfs(k, -1, dist3)\n",
    "        depth = [0] * n \n",
    "        for i in range(n):\n",
    "            depth[i] = max(dist2[i], dist3[i])\n",
    "        \n",
    "        res = []\n",
    "        mi = inf\n",
    "        for i in range(n):\n",
    "            if depth[i] < mi:\n",
    "                mi = depth[i]\n",
    "        \n",
    "        for i in range(n):\n",
    "            if depth[i] == mi:\n",
    "                res.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def dfs1(self, graph: List[List[int]], height0: List[int], u: int) -> None:\n",
    "        height0[u] = 1\n",
    "        h = 0\n",
    "        for v in graph[u]:\n",
    "            if height0[v] != 0:\n",
    "                continue\n",
    "            self.dfs1(graph, height0, v)\n",
    "            h = max(h, height0[v])\n",
    "        height0[u] = h + 1\n",
    "\n",
    "    def dfs2(self, graph: List[List[int]], height0: List[int], height: List[int], u: int) -> None:\n",
    "        first, second = 0, 0\n",
    "        for v in graph[u]:\n",
    "            if height0[v] > first:\n",
    "                second, first = first, height0[v]\n",
    "            elif height0[v] > second:\n",
    "                second = height0[v]\n",
    "        height[u] = first + 1\n",
    "        for v in graph[u]:\n",
    "            if height[v] != 0:\n",
    "                continue\n",
    "            height0[u] = first + 1 if height0[v] != first else second + 1\n",
    "            self.dfs2(graph, height0, height, v)\n",
    "\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            graph[e[0]].append(e[1])\n",
    "            graph[e[1]].append(e[0])\n",
    "\n",
    "        height0 = [0] * n\n",
    "        height = [0] * n\n",
    "        self.dfs1(graph, height0, 0)\n",
    "        self.dfs2(graph, height0, height, 0)\n",
    "\n",
    "        ans = []\n",
    "        h = n\n",
    "        for i in range(n):\n",
    "            if height[i] < h:\n",
    "                h = height[i]\n",
    "                ans.clear()\n",
    "            if height[i] == h:\n",
    "                ans.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    ## 查找 graph 里面距离 start 最远的节点\n",
    "    def bfs(self, n, graph, start):\n",
    "        visited  = [0]*n\n",
    "        visited[start] = 1\n",
    "        q = collections.deque()\n",
    "        q.append(start)\n",
    "        res = [start]\n",
    "        while len(q) > 0:\n",
    "            len_q = len(q)\n",
    "            for i in range(len_q):\n",
    "                top = q.popleft()\n",
    "                for x in graph[top]:\n",
    "                    if visited[x] == 0:\n",
    "                        q.append(x)\n",
    "                        res.append(x)\n",
    "                        visited[x] = 1\n",
    "                        graph[x].remove(top)\n",
    "        return res[-1]\n",
    "\n",
    "    ## 思路, 找出最长路径，然后找出其中的中间节点\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if len(edges) == 0:\n",
    "            return [0]\n",
    "        graph = [set() for i in range(n)]\n",
    "        for x in edges:\n",
    "            graph[x[0]].add(x[1])\n",
    "            graph[x[1]].add(x[0])\n",
    "        graph1 = copy.deepcopy(graph)\n",
    "        node1 = self.bfs(n, graph1, 0)\n",
    "        graph1 = copy.deepcopy(graph)\n",
    "        node2 = self.bfs(n, graph1, node1)  ## node1, node2 为图中的最长路径\n",
    "        father = [0]*n\n",
    "        q = collections.deque([node1])\n",
    "        visited = [0]*n\n",
    "        visited[node1] = 1\n",
    "        ## 广度遍历, 记录每个节点的 father 节点\n",
    "        while len(q) > 0:\n",
    "            len_q = len(q)\n",
    "            for i in range(len_q):\n",
    "                top = q.popleft()\n",
    "                if top == node2:\n",
    "                    break\n",
    "                for x in graph[top]:\n",
    "                    if visited[x] == 0:\n",
    "                        q.append(x)\n",
    "                        visited[x] = 1\n",
    "                        father[x] = top\n",
    "                        graph[x].remove(top)\n",
    "        tmp = [node2]\n",
    "        node = node2\n",
    "        while node != node1:\n",
    "            node = father[node]\n",
    "            tmp.append(node)\n",
    "        if len(tmp)%2 == 0:\n",
    "            return [tmp[int((len(tmp)-1)/2)], tmp[int((len(tmp))/2)]]\n",
    "        else:\n",
    "            return [tmp[int(len(tmp)/2)]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        height0 = [0] * n\n",
    "        def dfs(x, fa):\n",
    "            height0[x] = 1\n",
    "            h = 0\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "                    h = max(h, height0[y])\n",
    "            height0[x] = h + 1\n",
    "        dfs(0, -1)\n",
    "        height = [0] * n\n",
    "        def reroot(x, fa):\n",
    "            first, second = 0, 0\n",
    "            for y in g[x]:\n",
    "                if height0[y] > first:\n",
    "                    second = first\n",
    "                    first = height0[y]\n",
    "                elif height0[y] > second:\n",
    "                    second = height0[y]\n",
    "            height[x] = first + 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    height0[x] = (first if height0[y] != first else second) + 1 \n",
    "                    reroot(y, x)\n",
    "        reroot(0, -1)\n",
    "        ans = []\n",
    "        h = n\n",
    "        for i in range(n):\n",
    "            if height[i] < h:\n",
    "                h = height[i]\n",
    "                ans = []\n",
    "            if height[i] == h:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, xys: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in xys:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def bfs(x: int) -> int:\n",
    "            vis = [False for _ in range(n)]\n",
    "            que = deque()\n",
    "            vis[x] = True\n",
    "            que.append(x)\n",
    "            while que:\n",
    "                x = que.popleft()\n",
    "                for y in g[x]:\n",
    "                    if vis[y]: continue\n",
    "                    vis[y] = True\n",
    "                    que.append(y)\n",
    "            return x\n",
    "        src = bfs(0)\n",
    "        dst = bfs(src)\n",
    "\n",
    "        ans = None\n",
    "        path = []\n",
    "        vis = [False for _ in range(n)]\n",
    "        def dfs(x: int):\n",
    "            if x == dst:\n",
    "                nonlocal ans\n",
    "                ans = path.copy()\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if vis[y]: continue\n",
    "                vis[y] = True\n",
    "                path.append(y)\n",
    "                dfs(y)\n",
    "                path.pop()\n",
    "\n",
    "        vis[src] = True\n",
    "        path.append(src)\n",
    "        dfs(src)\n",
    "\n",
    "        n = len(ans)\n",
    "        if n % 2 == 0:\n",
    "            return [ans[n//2-1], ans[n//2]]\n",
    "        else:\n",
    "            return [ans[(n-1)//2]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        parents = [0] * n\n",
    "        maxDepth, node = 0, -1\n",
    "\n",
    "        def dfs(x, pa, depth):\n",
    "            nonlocal maxDepth, node\n",
    "            if depth > maxDepth:\n",
    "                maxDepth, node = depth, x\n",
    "            parents[x] = pa\n",
    "            for y in g[x]:\n",
    "                if y != pa:\n",
    "                    dfs(y, x, depth+1)\n",
    "        dfs(0, -1, 1)\n",
    "        maxDepth = 0\n",
    "        dfs(node, -1, 1)\n",
    "\n",
    "        path = []\n",
    "        while node != -1:\n",
    "            path.append(node)\n",
    "            node = parents[node]\n",
    "        m = len(path)\n",
    "        return [path[m // 2]] if m % 2 else [path[m // 2 - 1], path[m // 2]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        # g = [[] for _ in range(n)]\n",
    "        # deg = [0] * n\n",
    "        # for x, y in edges:\n",
    "        #     g[x].append(y)\n",
    "        #     g[y].append(x)\n",
    "        #     deg[x] += 1\n",
    "        #     deg[y] += 1\n",
    "        # q = [i for i, d in enumerate(deg) if d == 1]\n",
    "        # remained = n\n",
    "        # while remained > 2:\n",
    "        #     remained -= len(q)\n",
    "        #     tmp = q\n",
    "        #     q = []\n",
    "        #     for x in tmp:\n",
    "        #         for y in g[x]:\n",
    "        #             deg[y] -= 1\n",
    "        #             if deg[y] == 1:\n",
    "        #                 q.append(y)\n",
    "        # return q\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        parents = [0] * n\n",
    "        maxDepth, node = 0, -1\n",
    "\n",
    "        def dfs(x, pa, depth):\n",
    "            nonlocal maxDepth, node\n",
    "            if depth > maxDepth:\n",
    "                maxDepth, node = depth, x\n",
    "            parents[x] = pa\n",
    "            for y in g[x]:\n",
    "                if y != pa:\n",
    "                    dfs(y, x, depth + 1)\n",
    "        \n",
    "        dfs(0, -1, 1)\n",
    "        maxDepth = 0\n",
    "        dfs(node, -1, 1)\n",
    "        \n",
    "        path = []\n",
    "        while node != -1:\n",
    "            path.append(node)\n",
    "            node = parents[node]\n",
    "        m = len(path)\n",
    "        return [path[m // 2]] if m % 2 > 0 else [path[m // 2 - 1], path[m // 2]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        down1 = [0] * n\n",
    "        down2 = [0] * n\n",
    "        ne = [0] * n\n",
    "        def dfs(u, fa):\n",
    "            for y in g[u]:\n",
    "                if y == fa: continue\n",
    "                dfs(y, u)\n",
    "                height = down1[y] + 1\n",
    "                if height >= down1[u]:\n",
    "                    down1[u], down2[u] = height, down1[u]\n",
    "                    ne[u] = y\n",
    "                elif height >= down2[u]:\n",
    "                    down2[u] = height\n",
    "        up = [0] * n\n",
    "        def reroot(u, fa):\n",
    "            for y in g[u]:\n",
    "                if y == fa: continue\n",
    "                if ne[u] == y:\n",
    "                    up[y] = max(down2[u], up[u]) + 1\n",
    "                else:\n",
    "                    up[y] = max(down1[u], up[u]) + 1\n",
    "                reroot(y, u)\n",
    "        dfs(0, -1)\n",
    "        reroot(0, -1)\n",
    "        min_h = min(max(u, d) for u, d in zip(down1, up))\n",
    "        ans = [node for node in range(n) if max(down1[node], up[node]) == min_h]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def dfs1(node,p):\n",
    "            if len(g[node])==1 and p!=-1:\n",
    "                return 0\n",
    "            for y in g[node]:\n",
    "                if y==p:\n",
    "                    continue\n",
    "                sub=dfs1(y,node)+1\n",
    "                if sub>f1[node]:\n",
    "                    f2[node]=f1[node]\n",
    "                    f1[node]=sub\n",
    "                    pa[node]=y\n",
    "                elif sub>f2[node]:\n",
    "                    f2[node]=sub\n",
    "            return f1[node]\n",
    "        \n",
    "        def dfs(node,p):\n",
    "            for y in g[node]:\n",
    "                if y==p:\n",
    "                    continue\n",
    "                if y==pa[node]:\n",
    "                    up[y]=max(up[y],f2[node]+1)\n",
    "                else:\n",
    "                    up[y]=max(up[y],f1[node]+1)\n",
    "                up[y]=max(up[y],up[node]+1)\n",
    "                dfs(y,node)\n",
    "            \n",
    "        g=[[] for _ in range(n)]\n",
    "        for x in edges:\n",
    "            i=x[0]\n",
    "            j=x[1]\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        f1=[0]*n\n",
    "        f2=[0]*n\n",
    "        pa=[0]*n\n",
    "        up=[0]*n\n",
    "\n",
    "        dfs1(0,-1)\n",
    "        dfs(0,-1)\n",
    "\n",
    "        ans=[]\n",
    "        mh=inf\n",
    "\n",
    "        for i in range(n):\n",
    "            lenth=max(f1[i],up[i])\n",
    "            if lenth<mh:\n",
    "                ans.clear()\n",
    "                ans.append(i)\n",
    "                mh=lenth\n",
    "            elif lenth==mh:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
